package heap_1101;

public class Heap操作练习 {
    public static void adjustDownSmallHeap递归 (int array[],int index) {
        int parent = index;//需要调整的元素下标
        int child = 2 * parent + 1;//假设最小孩子是左孩子
        //判断右孩子是否存在，找出左右孩子中最小的一个
        if(child>=array.length){
            return ;
        }
        if (child + 1 < array.length && array[child] > array[child + 1]) {
            child += 1;//如果右孩子存在，并且更小，就把右孩子定为最小孩子
        }
        if (array[parent] <= array[child]) {//当待调整元素小于等于最小孩子，则代表满足小堆性质
            return;
        }
        //否则不满足堆的性质
        //向下调整，就是和最小孩子交换
        int tmp = array[parent];
        array[parent] = array[child];
        array[child] = tmp;

        //递归
        adjustDownSmallHeap递归(array,child);
    }
    public static void adjustDownSmallHeap (int array[],int index) {
        int parent = index;//需要调整的元素下标
        int child = 2 * parent + 1;//假设最小孩子是左孩子
        //判断右孩子是否存在，找出左右孩子中最小的一个

        while (child < array.length) {//孩子结点存在
            if (child + 1 < array.length && array[child] > array[child + 1]) {
                child += 1;//如果右孩子存在，并且更小，就把右孩子定为最小孩子
            }
            if (array[parent] <= array[child]) {//当待调整元素小于等于最小孩子，则代表满足小堆性质
                break;//跳出循环
            }
            //向下调整，就是和最小孩子交换
            int tmp = array[parent];
            array[parent] = array[child];
            array[child] = tmp;

            // parent中大的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
            parent = child;//改变需要调整的元素下标和最小孩子的下标
            child = 2 * parent + 1;
        }
    }
    public static void adjustDownBigHeap (int array[],int index) {
        int parent = index;//需要调整的元素下标
        int child = 2 * parent + 1;//假设最大孩子是左孩子
        //判断右孩子是否存在，找出左右孩子中最大的一个

        while (child < array.length) {//孩子结点存在
            if (child + 1 < array.length && array[child] < array[child + 1]) {
                child += 1;//如果右孩子存在，并且更大，就把右孩子定为最大孩子
            }
            if (array[parent] >= array[child]) {//当待调整元素大于等于最小孩子，则代表满足大堆性质
                break;//跳出循环
            }
            //向下调整，就是和最大孩子交换
            int tmp = array[parent];
            array[parent] = array[child];
            array[child] = tmp;

            // parent中小的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
            parent = child;//改变需要调整的元素下标和最大孩子的下标
            child = 2 * parent + 1;
        }
    }
    public static void adjustDownBigHeap递归 (int array[],int index) {
        int parent = index;//需要调整的元素下标
        int child = 2 * parent + 1;//假设最大孩子是左孩子
        //判断右孩子是否存在，找出左右孩子中最大的一个
        if (child + 1 < array.length && array[child] < array[child + 1]) {
            child += 1;//如果右孩子存在，并且更大，就把右孩子定为最大孩子
        }
        if (array[parent] >= array[child]) {//当待调整元素大于等于最小孩子，则代表满足大堆性质
            return;//跳出循环
        }

        //否则不满足堆的性质
        //向下调整，就是和最大孩子交换
        int tmp = array[parent];
        array[parent] = array[child];
        array[child] = tmp;

        adjustDownBigHeap递归(array,child);
    }
    public static void createBigHeap (int array[]){
        int parentIndex=(array.length-1-1)/2;//array.length-1是最后一个叶子结点的位置，（i-1）/2是求父亲结点的公式
        for(int i=parentIndex;i>=0;i--){
            adjustDownBigHeap(array,i);
        }
    }
    public static void createSmallHeap (int array[]){
        int parentIndex=(array.length-1-1)/2;//array.length-1是最后一个叶子结点的位置，（i-1）/2是求父亲结点的公式
        for(int i=parentIndex;i>=0;i--){
            adjustDownSmallHeap(array,i);
        }
    }

    public static void main(String[] args) {
        int array[]={9,3,1,7,6,9,5,8,4,0,0,3,6,4,1};
        createSmallHeap(array);
    }
}
